|
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If a tail call might lead to the same subroutine being called again later in the call chain, the subroutine is said to be tail-recursive, which is a special case of recursion. Tail recursion (or tail-end recursion) is particularly useful, and often easy to handle in implementations. Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination. Tail call elimination allows procedure calls in tail position to be implemented as efficiently as goto statements, thus allowing efficient structured programming. In the words of Guy L. Steele, "in general procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly coded as (code ) JUMP instructions."〔 Traditionally, tail call elimination is optional. However, in functional programming languages, tail call elimination is often guaranteed by the language standard, and this guarantee allows using recursion, in particular tail recursion, in place of loops. In such cases, it is not correct (though it may be customary) to refer to it as an optimization. The special case of tail recursive calls, when a function calls itself, may be more amenable to call elimination than general tail calls. ==Description== When a function is called, the computer must "remember" the place it was called from, the ''return address'', so that it can return to that location with the result once the call is complete. Typically, this information is saved on the call stack, a simple list of return locations in order of the times that the call locations they describe were reached. For tail calls, there is no need to remember the place we are calling from – instead, we can perform tail call elimination by leaving the stack alone (except possibly for function arguments and local variables), and the newly called function will return its result directly to the ''original'' caller. Note that the tail call doesn't have to appear lexically after all other statements in the source code; it is only important that the calling function return immediately after the tail call, returning the tail call's result if any, since the calling function will never get a chance to do anything after the call if the optimization is performed. For non-recursive function calls, this is usually an optimization that saves little time and space, since there are not that many different functions available to call. When dealing with recursive or mutually recursive functions where recursion happens through tail calls, however, the stack space and the number of returns saved can grow to be very significant, since a function can call itself, directly or indirectly, creating new call stacks each iteration. In fact, it often asymptotically reduces stack space requirements from linear, or O(n), to constant, or O(1). Tail call elimination is thus required by the standard definitions of some programming languages, such as Scheme, and languages in the ML family among others. In the case of Scheme, the language definition formalizes the intuitive notion of tail position exactly, by specifying which syntactic forms allow having results in tail context. Implementations allowing an unlimited number of tail calls to be active at the same moment, thanks to tail call elimination, can also be called 'properly tail-recursive'.〔 Besides space and execution efficiency, tail call elimination is important in the functional programming idiom known as continuation-passing style (CPS), which would otherwise quickly run out of stack space. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「tail call」の詳細全文を読む スポンサード リンク
|